package BinaryTreeExer;

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-21
 * Time: 15:21
 */

/**
 * 二叉树遍历:

 * warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
 * 描述
 * 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
 * 输入描述：
 * 输入包括1行字符串，长度不超过100。
 * 输出描述：
 * 可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
 * 示例1
 * 输入：
 * abc##de#g##f###
 * 复制
 * 输出：
 * c b e g d f a
 */

public class BinaryExercise3 {

    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inorderTree(root);
        }
    }


    //创建二叉树：
    //遍历字符串的全局变量，局部变量递归时会把i置0
    public static int i = 0;

    public static TreeNode createTree(String str) {
        TreeNode root = null;
        if(str.charAt(i) != '#') {
            //先创建一个根节点
            root = new TreeNode(str.charAt(i));

            //创建好，i往后走，创建左右子树的各个节点
            i++;

            root.left = createTree(str);
            root.right = createTree(str);

        }else {
            i++;
        }

        return root;
    }

    //中序遍历打印二叉树
    public static void inorderTree(TreeNode root) {
        if(root == null) {
            return;
        }
        inorderTree(root.left);
        System.out.print(root.val + " ");
        inorderTree(root.right);
    }
}
